package commonusealgorithm;

/**
 * @Author PoX21s
 * @Date: 2021/10/31 16:09
 * @Version 1.0
 */
/*
* - 设定了每一个物品的价值和重量
* - 背包中每一个物品只能放一件
* */
public class KnapsackProblem {
    public static void main(String[] args) {
        int[] val = {1500, 3000, 2000};
        int[] wight = {1, 4, 3};
        int pack = 4;
        int[][] path = new int[val.length+1][pack+1];
        // 创建数组来存储背包中放入物品以后的价值
        int[][] v =  new int[val.length+1][pack+1];
        // 从第二行和第二列开始遍历，因此第一行和第一列的值都为0，则对于加入第一个物品可以放入背包时
        // 可以参考前面没有物品可以放所得到的解
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                // 当前加入的物品一定要小于或等于背包当前的重量，这样才能够放入
                if (j >= wight[i-1]){
                    // 在加入新的物品以后，尝试把它放入背包，并且把空余的位置放能够放下的物品
                    // 与和没有加入这个物品时，在这个重量下背包能够得到的最优解进行比较，如果大于，则将这个值
                    // 放放入v二维数组中
                    if (v[i-1][j] < val[i-1]+v[i-1][j-wight[i-1]]){
                        v[i][j] =val[i-1]+v[i-1][j-wight[i-1]];
                        // 创建这个数组来保存这个重量下得到最优解放入了哪些物品
                        // 这里是一定放入i-1这个物品的，剩下的重量则是用其他物品进行填充的
                        // 这个j可以参考v[i-1][j-wight[i-1]]放入的物品，这样就可以得到当时背包中放入的物品
                        path[i][j] = 1;
                    } else {
                        // 如果加入物品的解不能比不加入这个物品的解更优，则用上一个同样重量背包但是物品更少得解来赋值
                        v[i][j] =v[i-1][j];
                    }
                } else {
                    // 如果放入的物品的重量大于背包的容量，则也是直接用上一个同样重量下得到的解
                    v[i][j] = v[i-1][j];
                }
            }
        }

        // 输出
        for (int[] ints : v) {
            for (int anInt : ints) {
                System.out.printf("%6d",anInt);
            }
            System.out.println();
        }
        /*
        * 这里也可以输出patch数组，如果数组中的值为1，则进行输出，说明这个背包是组合的，
        * 遍历出的一维数组上的变量则为放入的物品，二维数组上的变量则可以参考前面遍历出的一维数组相同的变量
        * 可以理解一下上面赋值所写的注释
        * */
    }
}

/*
        System.out.println("放入情况：（注：物品从1开始，0则代表没有这个物品）");
                for (int i = 1; i < path.length; i++) {
        for (int j = 1; j < path[0].length; j++) {
        if (path[i][j] != 0){
        if (j-i > 0){
        System.out.printf("有%d个物品可以放入，重量为%d",i,j);
        System.out.println();
        System.out.printf("放入的物品为%d和另外一个重量为%d的物品（可能是组合）",i,j-i);
        System.out.println();
        }
        System.out.println();
        }
        }
        System.out.println();
        }
*/


/*                if (i == 1 && j >= wight[0]){
                    v[i][j] = val[0];
                } else if (i == 2){
                    if (j >= wight[1]){
                        v[i][j] = Math.max(val[i-1],val[i-1]+v[i-1][j-wight[i-1]]);
                    } else {
                        v[i][j] = v[i-1][j];
                    }
                } else if (i == 3){
                    if (j >= wight[2]){
                        v[i][j] = Math.max(val[i-1],val[i-1]+v[i-1][j-wight[i-1]]);
                    } else {
                        v[i][j] = v[i-1][j];
                    }
                }*/
//            v[i][j] = Math.max(val[i-1],val[i-1]+v[i-1][j-wight[i-1]]);